package binarytree

// 递归
func sumOfLeftLeaves(root *TreeNode) int {
	res := 0
	var helper func(root *TreeNode)
	helper = func(root *TreeNode) {
		if root == nil {
			return
		}

		if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
			res += root.Left.Val
		}

		helper(root.Left)
		helper(root.Right)
	}
	helper(root)
	return res
}

// 迭代
func sumOfLeftLeaves2(root *TreeNode) int {

	// 只有根节点
	if root == nil || (root.Left == nil && root.Right == nil) {
		return 0
	}

	sum := 0
	stack := []*TreeNode{root}

	for len(stack) != 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		// 左节点为叶子结点
		if node.Left != nil && node.Left.Left == nil && node.Left.Right == nil {
			sum += node.Left.Val

			if node.Right != nil {
				stack = append(stack, node.Right)
			}
			continue
		}

		if node.Left != nil {
			stack = append(stack, node.Left)
		}

		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}

	return sum

}
